#include "graph.h"
#include <string>
#include <fstream>
#include <iostream>
#include <chrono>

std::string Edge::to_str() const
{
    std::string str = "";
    str += "id: " + std::to_string(id) + " ";
    str += "s: " + std::to_string(u) + " ";
    str += "t: " + std::to_string(v) + " ";
    str += "u: " + std::to_string(t) + " ";
    str += "v: " + std::to_string(w) + "\n";
    return str;
}

ADJ::ADJ(std::string filename)
{
    std::ifstream infile(filename);
    int n = 0, m = 0, u, v;
    std::string help;
    time_t t, w = 1;
    if (infile.is_open()) {
        while (!infile.eof()) {
            infile >> u >> v >> help >> t;
            m++;
            this->vertices.emplace(u);
            this->vertices.emplace(v);
            edges[m] = {m, u, v, t, w};
            this->out[u].emplace(m, u, v, t, w);
            this->in[v].emplace(m, u, v, t, w);
        }
    }
    this->n = vertices.size();
    this->m = edges.size();
}

OSE ADJ::to_OSE()
{
    OSE ose;
    ose.n = n;
    ose.m = m;
    ose.vertices = vertices;
    for (auto& [k, v]: edges) {
        ose.edges.insert(v);
    }
    return ose;
}

void ADJ::caculate(int x, time_t ta, time_t to)
{
    f.clear();
    L.clear();
    dis.clear();
    c.clear();
    pe.clear();
    ps.clear();
    source = x;
    start = ta;
    end = to;
    dis[std::make_pair(x, ta)] = 0;
    pq.emplace(0, ta, x, -1, -1, -1);
    while (!pq.empty()) {
        auto [d, t, u, pu, pt, peid] = pq.top();
        pq.pop();
        if (!L.contains(u) || L[u].begin()->first > t) {
            L[u].insert(L[u].begin(), std::make_pair(t, d));
            if (peid != -1) {
                ps[std::make_pair(u, t)] = std::make_pair(pu, pt);
                pe[std::make_pair(u, t)] = edges[peid];
                c[{pu, pt}].emplace(u, t);
            }
            if (!f.contains(u)) {
                f[u] = d;
            }
            Edge bound_edge = {-1, -1, -1, t, 0 };
            for (auto it= out[u].lower_bound(bound_edge); it != out[u].end(); it++) {
                auto [nid, nu, nv, nt, nw] = *it;
                if (nt > to) break;
                if (nt + nw > to) continue;
                time_t na = nt + nw;
                int nd = d + nw;
                if (!L.contains(nv) || L[nv].begin()->first > na) {
                    if (!dis.contains(std::make_pair(nv, na)) || dis[std::make_pair(nv, na)] > nd) {
                        dis[std::make_pair(nv, na)] = nd;
                        pq.emplace(nd, na, nv, u, t, nid); 
                    }
                }
            }
        }
    }
}

bool ADJ::has_domi(int u, time_t a, int d) {
    if (!L.contains(u)) {
        return false;
    }
    auto it = L[u].upper_bound(a);
    if (it == L[u].begin() || prev(it)->second > d) {
        return false;
    }
    return true;
}

bool ADJ::domi_insert(int u, time_t a, int d) {
    if (!L.contains(u)) {
        L[u][a] = d;
        return true;
    }
    if (L[u].contains(a) && L[u][a] <= d) {
        return false;
    }
    auto it = L[u].lower_bound(a);
    if (it == L[u].begin() || prev(it)->second > d) {
        while (it != L[u].end() && it->second >= d) {
            auto [da, dd] = *it;
            if (dd == d) {
                for (std::pair<int, long long int> cs: c[{u, da}]) {
                    ps[cs] = {u, a};
                    c[{u, a}].emplace(cs);
                }
            }
            it = L[u].erase(it);
            std::pair<int, time_t> pss = ps[{u, da}];
            c[pss].erase({u, da});
            ps.erase({u, da});
            pe.erase({u, da});
        }
        L[u].insert(it, {a,d});
        return true;
    }
    return false;
}

void ADJ::add_edges(std::vector<Edge> new_edges) {
    dis.clear();
    for (auto& new_edge: new_edges) {
        auto [id, u, v, t, w] = new_edge;
        vertices.emplace(u);
        vertices.emplace(v);
        edges[id] = new_edge;
        out[u].insert(new_edge);
        in[v].insert(new_edge);
        n = vertices.size();
        m = edges.size();
        if (t >= start && t + w <= end) {
            if (L.contains(u)) {
                auto it = L[u].upper_bound(t);
                if (it != L[u].begin()) {
                    auto [pa, pd] = *prev(it);
                    time_t na = t + w;
                    int nd = pd + w;
                    if (has_domi(v, na, nd)) continue;
                    if (!dis.contains({v, na}) || dis[{v, na}] > nd) {
                        dis[{v, na}] = nd;
                        pq.emplace(nd, na, v, u, pa, id);
                    }
                }
            }
        }
    }
    while (!pq.empty()) {
        auto [d, t, u, pu, pt, peid] = pq.top();
        pq.pop();
        if (domi_insert(u, t, d)) {
            ps[std::make_pair(u, t)] = std::make_pair(pu, pt);
            pe[std::make_pair(u, t)] = edges[peid];
            c[std::make_pair(pu, pt)].emplace(u, t);
            if (!f.contains(u) || f[u] > d) {
                f[u] = d;
            }
            Edge bound_edge = {-1, -1, -1, t, 0 };
            time_t right_bound = end;
            auto right_bound_it = L[u].upper_bound(t);
            if (right_bound_it != L[u].end()) {
                right_bound = right_bound_it->first;
            }
            for (auto it = out[u].lower_bound(bound_edge); it != out[u].end(); it++) {
                auto [nid, nu, nv, nt, nw] = *it;
                if (nt >= right_bound) break;
                if (nt > end) break;
                if (nt + nw > end) continue;
                time_t na = nt + nw;
                int nd = d + nw;
                if (has_domi(nu, nt, nd)) {
                    if (!dis.contains(std::make_pair(nv, na)) || dis[std::make_pair(nv, na)] > nd) {
                        dis[std::make_pair(nv, na)] = nd;
                        pq.emplace(nd, na, nv, u, t, nid);
                    }
                }
            }
        }
    }
}

void OSE::caculate(int x, time_t ta, time_t to)
{
    f.clear();
    L.clear();
    source = x;
    start = ta;
    end = to;
    f[x] = 0;
    std::vector<Edge> mt_edges;
//    for (auto& e : edges) {
//        mt_edges.push_back(e);
//    }
//    std::srand(unsigned(std::time(0)));
//    std::random_shuffle(mt_edges.begin(), mt_edges.end());
//    edges.clear();
//    for (auto& e : mt_edges) {
//        edges.insert(e);
//    }
    for (auto& e : edges) {
        if (e.t >= ta && e.t + e.w <= to) {
            if (e.u == x) {
                if (!L.contains(e.u)) {
                    L[e.u][e.t] = 0;
                }
            }
            if (L.contains(e.u)) {
                auto it = L[e.u].upper_bound(e.t);
                if (it != L[e.u].begin()) {
                    time_t a = e.t + e.w;
                    time_t pa = prev(it)->first;
                    int d = prev(it)->second + e.w;
                    if (L[e.v].contains(a) && L[e.v][a] <= d) {
                        continue;
                    }
                    it = L[e.v].lower_bound(a);
                    if (it == L[e.v].begin() || prev(it)->second > d) {
                        while (it != L[e.v].end() && it->second >= d) {
                            it = L[e.v].erase(it);
                        }
                        L[e.v].insert(it, std::make_pair(a, d));
                        ps[{e.v, a}] = {e.u, pa};
                        pe[{e.v, a}] = e;
                        if (!f.contains(e.v) || f[e.v] > d) {
                            f[e.v] = d;
                        }
                    }
                }
            }
        }
        else if (e.t >= to) {
            return;
        }
    }
}

void OSE::add_edges(std::vector<Edge> new_edges) {
    bool flag = false;
    for (auto& new_edge: new_edges) {
        if (new_edge.t >= start && new_edge.t + new_edge.w <= end) {
            flag = true;
        }
        edges.insert(new_edge);
        vertices.insert(new_edge.u);
        vertices.insert(new_edge.v);
    }
    n = vertices.size();
    m = edges.size();
    if (flag == true) {
        caculate(source, start, end);
    }
}

void OSE::delete_edges(std::vector<Edge> old_edges) {
    for (auto& old_edge: old_edges) {
        edges.erase(old_edge);
    }
    caculate(source, start, end);
}

void ADJ::re_add_edges(std::vector<Edge> new_edges) {
    for (auto& new_edge: new_edges) {
        auto [id, u, v, t, w] = new_edge;
        vertices.emplace(u);
        vertices.emplace(v);
        edges[id] = new_edge;
        out[u].insert(new_edge);
        in[v].insert(new_edge);
        n = vertices.size();
        m = edges.size();
    }
    caculate(source, start, end);
}

void ADJ::delete_edges(std::vector<Edge> old_edges) {
    red.clear();
    dis.clear();
    for (auto& old_edge: old_edges) {
        auto [id, u, v, t, w] = old_edge;
        edges.erase(id);
        out[u].erase(old_edge);
        in[v].erase(old_edge);
        if (pe.contains({v, t + w}) && pe[{v, t + w}].id == old_edge.id) {
            pq.emplace(L[v][t + w], t + w, v, 0, 0, id);
        }
    }
    while (!pq.empty()) {
        auto [d, t, u, pu, pt, peid] = pq.top();
        pq.pop();
        auto [bd, bt, bpu, bpt, bpeid] = find_best(u, t);
        if (bd == d && bt == t) {
            c[ps[{u, t}]].erase({u, t});
            ps[{u, t}] = {bpu, bpt};
            pe[{u, t}] = edges[bpeid];
            c[{bpu, bpt}].emplace(u, t);
        }
        else {
            red.emplace(u, t);
            for (auto& [child_u, child_t]: c[{u, t}]) {
                pq.emplace(L[child_u][child_t], child_t, child_u, 0, 0, 0);
            }
            c[ps[{u, t}]].erase({u, t});
            ps.erase({u, t});
            pe.erase({u, t});
            c.erase({u, t});
            L[u].erase(t);
            if (L[u].size() > 0) {
                f[u] = prev(L[u].end())->second;
            }
            else {
                f.erase(u);
            }
        }
    }
    for (auto [ru, rt]: red) {
        time_t left = rt, right = end;
        auto rit = L[ru].upper_bound(rt);
        if (rit != L[ru].end()) {
            right = rit->first;
        }
        Edge faker = {-1, -1, -1, left, 0};
        auto t = in[ru];
        for (auto it = in[ru].lower_bound(faker); it != in[ru].end(); it++) {
            auto [nid, nu, nv, nt, nw] = *it;
            if (nt + nw >= right) break;
            if (L.contains(nu)) {
                auto pit = L[nu].upper_bound(nt);
                if (pit != L[nu].begin()) {
                    int new_d = prev(pit)->second + nw;
                    time_t new_t = nt + nw;
                    if (has_domi(nv, new_t, new_d) == false) {
                        if (!dis.contains({nv, new_t}) || dis[{nv, new_t}] > new_d) {
                            dis[{nv, new_t}] = new_d;
                            pq.emplace(new_d, new_t, nv, nu, prev(pit)->first, nid);
                        }
                    }
                }
            }
        }
    }
    while (!pq.empty()) {
        auto [d, t, u, pu, pt, peid] = pq.top();
        pq.pop();
        if (domi_insert(u, t, d)) {
            ps[std::make_pair(u, t)] = std::make_pair(pu, pt);
            pe[std::make_pair(u, t)] = edges[peid];
            c[std::make_pair(pu, pt)].emplace(u, t);
            if (!f.contains(u) || f[u] > d) {
                f[u] = d;
            }
            Edge bound_edge = {-1, -1, -1, t, 0 };
            time_t right_bound = end;
            auto right_bound_it = L[u].upper_bound(t);
            if (right_bound_it != L[u].end()) {
                right_bound = right_bound_it->first;
            }
            for (auto it = out[u].lower_bound(bound_edge); it != out[u].end(); it++) {
                auto [nid, nu, nv, nt, nw] = *it;
                if (nt >= right_bound) break;
                if (nt > end) break;
                if (nt + nw > end) continue;
                time_t na = nt + nw;
                int nd = d + nw;
                if (has_domi(nu, nt, nd)) {
                    if (!dis.contains(std::make_pair(nv, na)) || dis[std::make_pair(nv, na)] > nd) {
                        dis[std::make_pair(nv, na)] = nd;
                        pq.emplace(nd, na, nv, u, t, nid);
                    }
                }
            }
        }
    }
}

std::tuple<int, time_t, int, time_t, int> ADJ::find_best(int ou, time_t ot) {
    time_t left = ot;
    time_t right = end;
    auto it = L[ou].upper_bound(ot);
    if (it != L[ou].end()) {
        right = it->first;
    }
    Edge fake = {-1, -1, -1, left, 0};
    int bd = -1, pu = -1;
    time_t bt = 0, pt = 0;
    int be = -1;
    for (auto it = in[ou].lower_bound(fake); it != in[ou].end(); it++) {
        auto [nid, nu, nv, nt, nw] = *it;
        if (nt + nw >= right) break;
        if (L.contains(nu)) {
            auto pit = L[nu].upper_bound(nt);
            if (pit != L[nu].begin()) {
                int new_d = prev(pit)->second + nw;
                time_t new_t = nt + nw;
                if (bd == -1 || new_d < bd) {
                    bd = new_d;
                    bt = new_t;
                    be = nid;
                    pu = nu;
                    pt = prev(pit)->first;
                }
            }
        }
    }
    return {bd, bt, pu, pt, be};
}

void ADJ::re_delete_edges(std::vector<Edge> old_edges) {
    for (auto& old_edge: old_edges) {
        auto [id, u, v, t, w] = old_edge;
        edges.erase(id);
        out[u].erase(old_edge);
        in[v].erase(old_edge);
        n = vertices.size();
        m = edges.size();
    }
    caculate(source, start, end);
}

void ADJ::path(int u, time_t t) {
    while (u != 0) {
        std::cout << pe[{u, t}].to_str();
        auto tu = ps[{u, t}].first;
        auto tt = ps[{u, t}].second;
        u = tu;
        t = tt;
    }
}

TRG ADJ::to_TRG() {
    TRG trg;
    std::unordered_map<int, std::set<time_t>> in_times;
    std::unordered_map<int, std::set<time_t>> out_times;
    for (auto& [key, value]: edges) {
        auto [id, u, v, t, w] = value;
        out_times[u].emplace(t);
        in_times[v].emplace(t + w);
        TRGEdge edge = {id, {u, t, 0}, {v, t + w, 1}, w};
        trg.edges[id] = edge;
        trg.out[{u, t, 0}].emplace(id);
        trg.in[{v, t + w, 1}].emplace(id);
        trg.m1++;
        trg.cnt[{u, t, 0}]++;
        trg.cnt[{v, t + w, 1}]++;
    }
    for (auto& [key, value]: out_times) {
        for (auto it = value.begin(); it != value.end(); it++) {
            if (next(it) != value.end()) {
                trg.m0--;
                trg.check[{key, *it, 0}] = trg.m0;
                TRGEdge edge = {trg.m0, {key, *it, 0}, {key, *next(it), 0}, 0};
                trg.edges[trg.m0] = edge;
                trg.out[{key, *it, 0}].emplace(trg.m0);
                trg.in[{key, *next(it), 0}].emplace(trg.m0);
            }
        }
    }
    for (auto& [key, value]: in_times) {
        for (auto it = value.begin(); it != value.end(); it++) {
            if (next(it) != value.end()) {
                trg.m0--;
                trg.check[{key, *it, 1}] = trg.m0;
                TRGEdge edge = {trg.m0, {key, *it, 1}, {key, *next(it), 1}, 0};
                trg.edges[trg.m0] = edge;
                trg.out[{key, *it, 1}].emplace(trg.m0);
                trg.in[{key, *next(it), 1}].emplace(trg.m0);
            }
        }
        if (out_times.contains(key)) {
            for (auto it = value.rbegin(); it != value.rend(); it++) {
                auto it2 = out_times[key].lower_bound(*it);
                if (it2 != out_times[key].end()) {
                    if (trg.check2.contains({key, *it2, 0})) continue;
                    trg.m0--;
                    trg.check2[{key, *it2, 0}] = trg.m0; // out to in
                    trg.check2[{key, *it, 1}] = trg.m0; // in to out
                    TRGEdge edge = {trg.m0, {key, *it, 1}, {key, *it2, 0}, 0};
                    trg.edges[trg.m0] = edge;
                    trg.out[{key, *it, 1}].emplace(trg.m0);
                    trg.in[{key, *it2, 0}].emplace(trg.m0);
                }
            }
        }
    }
    trg.in_times = in_times;
    trg.out_times = out_times;
    return trg;
}

void add_test(std::string filename) {
    for (int i = 1; i < 100; i++) {
        std::cout << i << std::endl;
        ADJ adj("");
        OSE ose = adj.to_OSE();
        ADJ test("");
        std::ifstream infile(filename);
        int n = 0, m = 0, u, v;
        std::string help;
        time_t t, w = 1;
        std::vector<Edge> new_edges;
        ose.caculate(i, 0, std::numeric_limits<time_t>::max());
        adj.caculate(i, 0, std::numeric_limits<time_t>::max());
        test.caculate(i, 0, std::numeric_limits<time_t>::max());
        if (infile.is_open()) {
            int help = 0;
            while (!infile.eof()) {
                infile >> u >> v >> help >> t;
                Edge new_edge = {m, u, v, t, w};
                new_edges.push_back(new_edge);
                m++;
                if (m % 1000 == 0) {
                    int before = ose.f.size();
                    auto start = std::chrono::system_clock::now();
                    ose.add_edges(new_edges);
                    auto end = std::chrono::system_clock::now();
                    auto duration = duration_cast<std::chrono::microseconds>(end - start);
                    std::cout << "ose" << " " << duration << " ";
                    start = std::chrono::system_clock::now();
                    adj.add_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    duration = duration_cast<std::chrono::microseconds>(end - start);
                    std::cout << "adj" << " " << duration << " ";
                    start = std::chrono::system_clock::now();
                    test.re_add_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    duration = duration_cast<std::chrono::microseconds>(end - start);
                    std::cout << "re adj" << " " << duration << std::endl;
                    new_edges.clear();
                    std::cout << "diff: " << ose.f.size() - before << std::endl;
                    help = ose.f.size();
                    if (ose.f.size() != adj.f.size()) {
                        std::cout << "error size!" << std::endl;
                        break;
                    }
                    for (auto [v, d]: ose.f) {
                        if (!adj.f.contains(v)) {
                            std::cout << "error ans1! " << v << "" << std::endl;
                            break;
                        }
                        if (adj.f[v] != d) {
                            std::cout << "error ans2!" << std::endl;
                            break;
                        }
                    }
                }
            }
        }
    }
}

void delete_test(std::string filename) {
    for (int i = 1; i < 100; i++) {
        std::cout << i << std::endl;
        ADJ adj(filename);
        OSE ose = adj.to_OSE();
        ADJ test(filename);
        std::ifstream infile(filename);
        int n = 0, m = 0, u, v;
        std::string help;
        time_t t, w = 1;
        std::vector<Edge> new_edges;
        ose.caculate(i, 0, std::numeric_limits<time_t>::max());
        adj.caculate(i, 0, std::numeric_limits<time_t>::max());
        test.caculate(i, 0, std::numeric_limits<time_t>::max());
//        for (auto [k, v]: test.ps) {
//            std::cout << k.first << " " << k.second << std::endl;
//            adj.path(k.first, k.second);
//            break;
//        }
        if (infile.is_open()) {
            int help = 0;
            while (!infile.eof()) {
                infile >> u >> v >> help >> t;
                m++;
                Edge new_edge = {m, u, v, t, w};
                new_edges.push_back(new_edge);
                if (m % 1000 == 0) {
                    int before = ose.f.size();
                    auto start = std::chrono::system_clock::now();
                    ose.delete_edges(new_edges);
                    auto end = std::chrono::system_clock::now();
                    auto duration = duration_cast<std::chrono::microseconds>(end - start);
                    std::cout << "ose" << " " << duration << " ";
                    start = std::chrono::system_clock::now();
                    adj.delete_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    duration = duration_cast<std::chrono::microseconds>(end - start);
                    std::cout << "adj" << " " << duration << " ";
                    start = std::chrono::system_clock::now();
                    test.re_delete_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    duration = duration_cast<std::chrono::microseconds>(end - start);
                    std::cout << "re adj" << " " << duration << std::endl;
                    new_edges.clear();
                    std::cout << "after " << before - ose.f.size() << std::endl;
//                    for (auto [k, v]: adj.ps) {
//                        std::cout << k.first << " " << k.second << std::endl;
//                        adj.path(k.first, k.second);
//                        break;
//                    }
                    if (ose.f.size() != adj.f.size()) {
                        for (auto [v, d]: ose.f) {
                            if (!adj.f.contains(v)) {
                                std::cout << v << " " << d << std::endl;
                            }
                        }
                        std::cout << "error size!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << std::endl;
                    }
                    for (auto [v, d]: adj.f) {
                        if (!ose.f.contains(v)) {
                            std::cout << "error ans1!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! " << v << "" << std::endl;
                            auto a = ose.L[v];
                            auto b = adj.L[v];
                            break;
                        }
                        if (ose.f[v] != d) {
                            std::cout << v << " " << d;
                                std::cout << " error ans2!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << std::endl;
                            break;
                        }
                    }
                }
            }
        }
    }
}

std::string TRGEdge::to_str() const {
    std::string s = "";
    s += std::to_string(id) + " " + std::to_string(std::get<0>(u)) + " " + std::to_string(std::get<1>(u)) + " " + std::to_string(std::get<2>(u)) + " " + std::to_string(std::get<0>(v)) + " " + std::to_string(std::get<1>(v)) + " " + std::to_string(std::get<2>(v)) + " " + std::to_string(w);
    return s;
}

void TRG::caculate(int x, time_t ta, time_t to) {
    source = x;
    start = ta;
    end = to;
    f.clear();
    ans.clear();
    pe.clear();
    c.clear();
    ans[x] = 0;
    for (auto time: out_times[x]) {
        if (time >= ta && time <= to) {
            pq.emplace(0, time, 0, x, 0);
            f[{x, time, 0}] = 0;
        }
    }
    while (!pq.empty()) {
        auto [d, t, io, u, eid] = pq.top();
        pq.pop();
        if (f.contains({u, t, io}) && f[{u, t, io}] < d) continue;
        if (eid != 0) {
            pe[{u, t, io}] = eid;
            c[edges[eid].u].emplace(u, t, io);
        }
        if (!ans.contains(u)) ans[u] = d;
        for (auto neid: out[{u, t, io}]) {
            auto [temp_id, nu, nv, nw] = edges[neid];
            if (std::get<1>(nv) >= start && std::get<1>(nv) <= end) {
                if (!f.contains(nv) || f[nv] > d + nw) {
                    pq.emplace(d + nw, std::get<1>(nv), std::get<2>(nv), std::get<0>(nv), neid);
                    f[nv] = d + nw;
                }
            }
        }
    }
}

void TRG::tadd_edges(std::vector<TRGEdge> new_edges) {
    for (auto e: new_edges) {
       edges[e.id] = e;
       out[e.u].insert(e.id);
       in[e.v].insert(e.id);
       if (std::get<0>(e.u) == source && std::get<1>(e.u) >= start && std::get<1>(e.u) <= end) f[e.u] = 0;
       if (!f.contains(e.u))    continue;
       if (!f.contains(e.v) || f[e.u] + e.w < f[e.v]) {
           auto [node, time, io] = e.v;
           if (time >= start && time <= end) {
               pq.emplace(f[e.u] + e.w, time, io, node, e.id);
           }
       }
    }
    while (!pq.empty()) {
        auto [d, t, io, u, eid] = pq.top();
        pq.pop();
        if (f.contains({u, t, io}) && f[{u, t, io}] <= d) continue;
        if (pe.contains({u, t, io})) {
            c[edges[pe[{u, t, io}]].u].erase({u, t, io});
        }
        f[{u, t, io}] = d;
        pe[{u, t, io}] = eid;
        c[edges[eid].u].emplace(u, t, io);
        if (!ans.contains(u) || ans[u] > d) ans[u] = d;
        for (auto neid: out[{u, t, io}]) {
            auto [temp_id, nu, nv, nw] = edges[neid];
            if (std::get<1>(nv) >= start && std::get<1>(nv) <= end) {
                if (!f.contains(nv) || f[nv] > d + nw) {
                    pq.emplace(d + nw, std::get<1>(nv), std::get<2>(nv), std::get<0>(nv), neid);
                }
            }
        }
    }
}

void TRG::tdelete_edges(std::vector<TRGEdge> old_edges) {
    red.clear();
    for (auto e: old_edges) {
        out[e.u].erase(e.id);
        in[e.v].erase(e.id);
        if (f.contains(e.v) && pe[e.v] == e.id) {
            auto [a, b, c] = e.v;
            pq.emplace(f[e.v], b, c, a, 0);
        }
    }
    while (!pq.empty()) {
        auto [d, t, io, u, eid] = pq.top();
        pq.pop();
        int bestd = -1, beste = 0;
        for (auto neid: in[{u, t, io}]) {
            auto [temp_id, nu, nv, nw] = edges[neid];
            if (std::get<1>(nu) >= start && std::get<1>(nu) <= end) {
                if (red.contains(nu)) continue;
                if (!f.contains(nu)) continue;
                if (bestd == -1 || f[nu] + nw < bestd) {
                    bestd = f[nu] + nw;
                    beste = neid;
                }
            }
        }
        if (bestd == d) {
            c[edges[pe[{u, t, io}]].u].erase({u, t, io});
            pe[{u, t, io}] = beste;
            c[edges[beste].u].emplace(u, t, io);
        }
        else {
            red.emplace(u, t, io);
            for (auto tt: c[{u, t, io}]) {
                pq.emplace(f[tt], std::get<1>(tt), std::get<2>(tt), std::get<0>(tt), 0);
            }
            c[edges[pe[{u, t, io}]].u].erase({u, t, io});
            pe.erase({u, t, io});
            f.erase({u, t, io});
            ans.erase(u);
        }
    }
    for (auto red_node: red) {
        int bestd = -1, beste = 0;
        for (auto neid: in[red_node]) {
            auto [temp_id, nu, nv, nw] = edges[neid];
            if (std::get<1>(nu) >= start && std::get<1>(nu) <= end) {
                if (red.contains(nu)) continue;
                if (!f.contains(nu)) continue;
                if (bestd == -1 || f[nu] + nw < bestd) {
                    bestd = f[nu] + nw;
                    beste = neid;
                }
            }
        }
        if (bestd == -1) continue;
        pq.emplace(bestd, std::get<1>(red_node), std::get<2>(red_node), std::get<0>(red_node), beste);
    }
    while (!pq.empty()) {
        auto [d, t, io, u, eid] = pq.top();
        pq.pop();
        if (f.contains({u, t, io}) && f[{u, t, io}] < d) continue;
        f[{u, t, io}] = d;
        pe[{u, t, io}] = eid;
        c[edges[eid].u].emplace(u, t, io);
        for (auto neid: out[{u, t, io}]) {
            auto [temp_id, nu, nv, nw] = edges[neid];
            if (std::get<1>(nv) >= start && std::get<1>(nv) <= end) {
                if (!f.contains(nv) || f[nv] > d + nw) {
                    pq.emplace(d+nw, std::get<1>(nv), std::get<2>(nv), std::get<0>(nv), neid);
                }
            }
        }
    }
    for (auto red_node: red) {
        auto [u, t, io] = red_node;
        if (ans.contains(u)) continue;
        if (in_times.contains(u)) {
            if (!in_times[u].empty()) {
                auto it = in_times[u].upper_bound(end);
                if (it != in_times[u].begin()) {
                    ans[u] = f[{u, *prev(it), 1}];
                }
            }
        }
    }
}

void TRG::real_delete_edges(std::vector<Edge> old_edges) {
    std::vector<TRGEdge> add_edges;
    std::vector<TRGEdge> delete_edges;
    for (auto& old_edge: old_edges) {
        delete_edges.push_back({old_edge.id, {old_edge.u, old_edge.t, 0}, {old_edge.v, old_edge.t + old_edge.w, 1}, old_edge.w});
        cnt[{old_edge.u, old_edge.t, 0}]--;
        cnt[{old_edge.v, old_edge.t + old_edge.w, 1}]--;
        if (cnt[{old_edge.u, old_edge.t, 0}] == 0) {
            auto it = out_times[old_edge.u].lower_bound(old_edge.t);
            if (it != out_times[old_edge.u].begin()) {
                delete_edges.push_back(edges[check[{old_edge.u, *prev(it), 0}]]);
                check.erase({old_edge.u, *prev(it), 0});
                if (next(it) != out_times[old_edge.u].end()) {
                    delete_edges.push_back(edges[check[{old_edge.u, *it, 0}]]);
                    check.erase({old_edge.u, *it, 0});
                    m0--;
                    add_edges.push_back({m0, {old_edge.u, *prev(it), 0}, {old_edge.u, *next(it), 0}, 0});
                    check[{old_edge.u, *prev(it), 0}] = m0;
                }
            }
            if (check2.contains({old_edge.u, old_edge.t, 0})) {
                auto& tedge = edges[check2[{old_edge.u, old_edge.t, 0}]];
                delete_edges.push_back(tedge);
                check2.erase(tedge.u);
                check2.erase(tedge.v);
                if (next(it) != out_times[old_edge.u].end()) {
                    if (*next(it) >= std::get<1>(tedge.u)) {
                        m0--;
                        add_edges.push_back({m0, tedge.u, {old_edge.u, *next(it), 0}, 0});
                        check2[{old_edge.u, *next(it), 0}] = m0;
                        check2[tedge.u] = m0;
                    }
                }
            }
            out_times[old_edge.u].erase(old_edge.t);
        }
        if (cnt[{old_edge.v, old_edge.t + old_edge.w, 1}] == 0) {
            auto it = in_times[old_edge.v].lower_bound(old_edge.t + old_edge.w);
            if (it != in_times[old_edge.v].begin()) {
                delete_edges.push_back(edges[check[{old_edge.v, *prev(it), 1}]]);
                check.erase({old_edge.v, *prev(it), 1});
                if (next(it) != in_times[old_edge.v].end()) {
                    delete_edges.push_back(edges[check[{old_edge.v, *it, 1}]]);
                    check.erase({old_edge.v, *it, 1});
                    m0--;
                    add_edges.push_back({m0, {old_edge.v, *prev(it), 1}, {old_edge.v, *next(it), 1}, 0});
                    check[{old_edge.v, *prev(it), 1}] = m0;
                }
            }
            if (check2.contains({old_edge.v, old_edge.t + old_edge.w, 1})) {
                auto& tedge = edges[check2[{old_edge.v, old_edge.t + old_edge.w, 1}]];
                delete_edges.push_back(tedge);
                check2.erase(tedge.u);
                check2.erase(tedge.v);
                if (it != in_times[old_edge.v].begin()) {
                    if (*prev(it) <= std::get<1>(tedge.v)) {
                        m0--;
                        add_edges.push_back({m0, {old_edge.v, *prev(it), 1}, tedge.v, 0});
                        check2[tedge.v] = m0;
                        check2[{old_edge.v, *prev(it), 1}] = m0;
                    }
                }
            }
            in_times[old_edge.v].erase(old_edge.t + old_edge.w);
        }
    }
    tadd_edges(add_edges);
    tdelete_edges(delete_edges);
}

void TRG::real_add_edges(std::vector<Edge> new_edges) {
    std::vector<TRGEdge> add_edges;
    std::vector<TRGEdge> delete_edges;
    for (auto& new_edge: new_edges) {
        m1++;
        add_edges.push_back({new_edge.id, {new_edge.u, new_edge.t, 0}, {new_edge.v, new_edge.t + new_edge.w, 1}, new_edge.w});
        cnt[{new_edge.u, new_edge.t, 0}]++;
        cnt[{new_edge.v, new_edge.t + new_edge.w, 1}]++;
        if (!out_times.contains(new_edge.u) || !out_times[new_edge.u].contains(new_edge.t)) {
            out_times[new_edge.u].emplace(new_edge.t);
            auto it = out_times[new_edge.u].lower_bound(new_edge.t);
            if (it != out_times[new_edge.u].begin()) {
                if (check.contains({new_edge.u, *prev(it), 0})) {
                    delete_edges.push_back(edges[check[{new_edge.u, *prev(it), 0}]]);
                }
                m0--;
                add_edges.push_back({m0, {new_edge.u, *prev(it), 0}, {new_edge.u, *it, 0}, 0});
                check[{new_edge.u, *prev(it), 0}] = m0;
            }
            if (next(it) != out_times[new_edge.u].end()) {
                m0--;
                add_edges.push_back({m0, {new_edge.u, *it, 0}, {new_edge.u, *next(it), 0}, 0});
                check[{new_edge.u, *it, 0}] = m0;
            }
            if (in_times.contains(new_edge.u)) {
                auto it2 = in_times[new_edge.u].upper_bound(new_edge.t);
                if (it2 != in_times[new_edge.u].begin()) {
                    time_t time = *prev(it2);
                    if (check2.contains({new_edge.u, time, 1})) {
                        TRGEdge& in_out_edge = edges[check2[{new_edge.u, time, 1}]];
                        if (std::get<1>(in_out_edge.v) > new_edge.t) {
                            delete_edges.push_back(edges[check2[{new_edge.u, time, 1}]]);
                            m0--;
                            add_edges.push_back({m0, {new_edge.u, time, 1}, {new_edge.u, new_edge.t, 0}, 0});
                            check2[{new_edge.u, new_edge.t, 0}] = m0;
                            check2[{new_edge.u, new_edge.t, 1}] = m0;
                        }
                    }
                }
            }
        }
        if (!in_times.contains(new_edge.v) || !in_times[new_edge.v].contains(new_edge.t + new_edge.w)) {
            in_times[new_edge.v].emplace(new_edge.t + new_edge.w);
            auto it = in_times[new_edge.v].lower_bound(new_edge.t + new_edge.w);
            if (it != in_times[new_edge.v].begin()) {
                if (check.contains({new_edge.v, *prev(it), 1})) {
                    delete_edges.push_back(edges[check[{new_edge.v, *prev(it), 1}]]);
                }
                m0--;
                add_edges.push_back({m0, {new_edge.v, *prev(it), 1}, {new_edge.v, *it, 1}, 0});
                check[{new_edge.v, *prev(it), 0}] = m0;
            }
            if (next(it) != in_times[new_edge.v].end()) {
                m0--;
                add_edges.push_back({m0, {new_edge.v, *it, 1}, {new_edge.v, *next(it), 1}, 0});
                check[{new_edge.v, *it, 0}] = m0;
            }
            if (out_times.contains(new_edge.v)) {
                auto it2 = out_times[new_edge.v].lower_bound(new_edge.t + new_edge.w);
                if (it2 != out_times[new_edge.v].end()) {
                    time_t time = *it2;
                    if (check2.contains({new_edge.v, time, 0})) {
                        TRGEdge& in_out_edge = edges[check2[{new_edge.v, time, 0}]];
                        if (std::get<1>(in_out_edge.u) < new_edge.t + new_edge.w) {
                            delete_edges.push_back(edges[check2[{new_edge.v, time, 0}]]);
                            m0--;
                            add_edges.push_back({m0, {new_edge.v, new_edge.t + new_edge.w, 1}, {new_edge.v, time, 0}, 0});
                            check2[{new_edge.v, new_edge.t + new_edge.w, 1}] = m0;
                            check2[{new_edge.v, time, 0}] = m0;
                        }
                    }
                }
            }
        }
    }
    tadd_edges(add_edges);
    tdelete_edges(delete_edges);
}

void delete_test2(std::string filename) {
    for (int i = 4; i < 100; i++) {
        std::cout << i << std::endl;
        ADJ adj(filename);
        OSE ose = adj.to_OSE();
        TRG trg = adj.to_TRG();
        std::ifstream infile(filename);
        int n = 0, m = 0, u, v;
        std::string help;
        time_t t, w = 1;
        std::vector<Edge> new_edges;
        ose.caculate(i, 0, std::numeric_limits<time_t>::max());
        trg.caculate(i, 0, std::numeric_limits<time_t>::max());
        if (infile.is_open()) {
            int help = 0;
            while (!infile.eof()) {
                infile >> u >> v >> help >> t;
                m++;
                Edge new_edge = {m, u, v, t, w};
                new_edges.push_back(new_edge);
                if (m % 10 == 0) {
                    auto start = std::chrono::system_clock::now();
                    ose.delete_edges(new_edges);
                    auto end = std::chrono::system_clock::now();
                    auto duration = duration_cast<std::chrono::microseconds>(end - start);
                    std::cout << "ose" << " " << duration << " ";
                    start = std::chrono::system_clock::now();
                    if (m == 120) {
                        std::cout << " ";
                    }
                    trg.real_delete_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    duration = duration_cast<std::chrono::microseconds>(end - start);
                    std::cout << "trg" << " " << duration << std::endl;
                    std::cout << "size" << " " << ose.f.size() << " " << trg.ans.size() << std::endl;
                    if (ose.f.size() != trg.ans.size()) {
                        std::cout << "error size!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << std::endl;
                    }
                    for (auto [v, d]: trg.ans) {
                        if (!ose.f.contains(v)) {
                            std::cout << "error ans1!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! " << v << "" << std::endl;
                        }
                        if (ose.f[v] != d) {
                            std::cout << v << " " << ose.f[v] << " " << d << std::endl;
                            std::cout << "error ans2!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! " << v << "" << std::endl;
                        }
                    }
                    new_edges.clear();
                }
            }
        }
    }
}

void add_test2(std::string filename) {
    for (int i = 1; i < 100; i++) {
        std::cout << i << std::endl;
        ADJ adj("");
        OSE ose = adj.to_OSE();
        TRG trg = adj.to_TRG();
        std::ifstream infile(filename);
        int n = 0, m = 0, u, v;
        std::string help;
        time_t t, w = 1;
        std::vector<Edge> new_edges;
        ose.caculate(i, 0, std::numeric_limits<time_t>::max());
        trg.caculate(i, 0, std::numeric_limits<time_t>::max());
        if (infile.is_open()) {
            int help = 0;
            while (!infile.eof()) {
                infile >> u >> v >> help >> t;
                m++;
                Edge new_edge = {m, u, v, t, w};
                new_edges.push_back(new_edge);
                if (m % 10 == 0) {
                    auto start = std::chrono::system_clock::now();
                    ose.add_edges(new_edges);
                    auto end = std::chrono::system_clock::now();
                    auto duration = duration_cast<std::chrono::microseconds>(end - start);
                    std::cout << "ose" << " " << duration << " ";
                    start = std::chrono::system_clock::now();
//                    if (m == 120) {
//                        std::cout << " ";
//                    }
                    trg.real_add_edges(new_edges);
                    end = std::chrono::system_clock::now();
                    duration = duration_cast<std::chrono::microseconds>(end - start);
                    std::cout << "trg" << " " << duration << std::endl;
                    std::cout << "size" << " " << ose.f.size() << " " << trg.ans.size() << std::endl;
                    if (ose.f.size() != trg.ans.size()) {
                        std::cout << "error size!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << std::endl;
                    }
                    for (auto [v, d]: trg.ans) {
                        if (!ose.f.contains(v)) {
                            std::cout << "error ans1!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! " << v << "" << std::endl;
                        }
                        if (ose.f[v] != d) {
                            std::cout << v << " " << ose.f[v] << " " << d << std::endl;
                            std::cout << "error ans2!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! " << v << "" << std::endl;
                        }
                    }
                    new_edges.clear();
                }
            }
        }
    }
}
